package codingforgreat.lchot150;

import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

public class Lc269 {
    //返回字母表或""
    public static String alienOrder(String[] words) {
        if(words == null || words.length == 0){
            return "";
        }
        HashMap<Character, HashSet<Character>> graph = new HashMap<>();
        HashMap<Character,Integer> indegree = new HashMap<>();
        int N = words.length;
        for(int i = 0;i < N;i++){
            for (char c : words[i].toCharArray()) {
                indegree.put(c, 0);
            }
        }
        for(int i = 0;i < N-1;i++){
            char[] cur = words[i].toCharArray();
            char[] next = words[i + 1].toCharArray();
            int minL = Math.min(cur.length,next.length);
            int j = 0;
            for(;j < minL;j++){
                if(cur[j] != next[j]){
                    if (!graph.containsKey(cur[j])) {
                        graph.put(cur[j], new HashSet<>());
                    }
                    if (!graph.get(cur[j]).contains(next[j])) {
                        graph.get(cur[j]).add(next[j]);
                        indegree.put(next[j], indegree.get(next[j]) + 1);
                    }
                    break;
                }
            }
            if (j < cur.length && j == next.length) {
                return "";
            }
        }
        // 找到入度为0的节点
        StringBuilder res = new StringBuilder();
        Queue<Character> zQ = new LinkedList<>();
        for (char c : indegree.keySet()) {
            if (indegree.get(c) == 0) {
                zQ.add(c);
            }
        }
        while(!zQ.isEmpty()){
            char c = zQ.poll();
            res.append(c);
            if(graph.containsKey(c)){
                for(char next : graph.get(c)){
                    indegree.put(next, indegree.get(next) - 1);
                    if(indegree.get(next) == 0){
                        zQ.add(next);
                    }
                }
            }
        }
        return res.length() == indegree.size() ? res.toString() : "";

    }
}
